////请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指
////向链表中的任意节点或者 null。
////
////
////
//// 示例 1：
////
////
////
//// 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
////输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
////
////
//// 示例 2：
////
////
////
//// 输入：head = [[1,1],[2,1]]
////输出：[[1,1],[2,1]]
////
////
//// 示例 3：
////
////
////
//// 输入：head = [[3,null],[3,0],[3,null]]
////输出：[[3,null],[3,0],[3,null]]
////
////
//// 示例 4：
////
//// 输入：head = []
////输出：[]
////解释：给定的链表为空（空指针），因此返回 null。
////
////
////
////
//// 提示：
////
////
//// -10000 <= Node.val <= 10000
//// Node.random 为空（null）或指向链表中的节点。
//// 节点数目不超过 1000 。
////
////
////
////
//// 注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-
////pointer/
////
////
//// Related Topics 哈希表 链表 👍 543 👎 0
//
//package leetcode.editor.cn;
//
//import java.util.HashMap;
//import java.util.Map;
//
////leetcode submit region begin(Prohibit modification and deletion)
///*
//// Definition for a Node.
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//*/
//
////class Node {
////    int val;
////    Node next;
////    Node random;
////
////    public Node(int val) {
////        this.val = val;
////        this.next = null;
////        this.random = null;
////    }
////}
//
//class SolutionOffer35 {
//    /**
//     * 哈希+递归
//     * @param head
//     * @return
//     */
//    Map<Node,Node> map = new HashMap<>();
//    public Node copyRandomList1(Node head) {
//        if(head == null){
//            return null;
//        }
//        if(!map.containsKey(head)){ //没有复制过
//            Node headNew = new Node(head.val);
//            map.put(head, headNew);
//            headNew.next = copyRandomList(head.next);
//            headNew.random = copyRandomList(head.random);
//        }
//        return map.get(head);
//    }
//
//
//    /**
//     * 哈希+迭代
//     * @param head
//     * @return
//     */
//    public Node copyRandomList2(Node head){
//        if(head == null) return null;
//        Node cur = head;
//        Map<Node,Node> map = new HashMap<>();
//        while (cur!= null){
//            map.put(cur,new Node(cur.val));
//            cur = cur.next;
//        }
//        cur = head;
//        while(cur != null){
//            map.get(cur).next = map.get(cur.next);
//            map.get(cur).random = map.get(cur.random);
//            cur = cur.next;
//        }
//        return map.get(head);
//    }
//
//    /**
//     * 拼接 + 拆分
//     */
//    public Node copyRandomList(Node head){
//        if(head == null) return null;
//        Node cur = head;
//        // 1. 复制各节点，并构建拼接链表
//        while(cur != null){
//            Node nodeNew = new Node(cur.val);
//            nodeNew.next = cur.next;
//            cur.next = nodeNew;
//            cur = cur.next.next;
//        }
//        // 2. 构建各新节点的 random 指向
//        cur = head;
//        while(cur!= null){
//            if(cur.random != null){
//                Node tmp = cur.random.next;
//                cur.next.random = tmp;
//            }
//            cur = cur.next.next;
//        }
//        // 3. 拆分两链表
//        cur = head.next;
//        while(cur != null){
//            cur.next = cur.next.next;
//            cur = cur.next;
//        }
//        return head.next;
//    }
//
//}
////leetcode submit region end(Prohibit modification and deletion)
